package zhengqc.graph.algorithm;

import zhengqc.graph.data_structure.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/* Unweighted-Graph Single Source Shortest Path
 * 无权图单源最短路径, 可同时适用于无权有向图和无权无向图 */
public class USSSP {
    private Graph graph;
    private int source;
    private boolean[] visited;
    private int[] precedes;
    private int[] distances;

    public USSSP(Graph graph, int source) {
        if (graph.isWeighted()) {
            throw new IllegalArgumentException("USSSP does't work in Weighted-Graph");
        }
        graph.validateVertex(source);
        this.graph = graph;
        this.source = source;
        this.visited = new boolean[graph.getV()];
        this.precedes = new int[graph.getV()];
        this.distances = new int[graph.getV()];
        for (int i = 0; i < graph.getV(); ++i) {
            precedes[i] = -1;
            distances[i] = -1;
        }
        bfs(source);
    }
    private void bfs(int source) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);
        this.visited[source] = true;
        this.precedes[source] = source;
        this.distances[source] = 0;
        while (!queue.isEmpty()) {
            int v = queue.remove();
            for (int w: this.graph.getAdjacency(v)) {
                if (!this.visited[w]) {
                    queue.add(w);
                    this.visited[w] = true;
                    this.precedes[w] = v;
                    this.distances[w] = this.distances[v] + 1;
                }
            }
        }
    }
    public boolean isConnectedTo(int target) {
        this.graph.validateVertex(target);
        return this.visited[target];
    }
    public Iterable<Integer> getPathTo(int target) {
        ArrayList<Integer> path = new ArrayList<>();
        if (!this.isConnectedTo(target)) {
            return path;
        }
        int current = target;
        while (current != this.source) {
            path.add(current);
            current = this.precedes[current];
        }
        path.add(this.source);
        Collections.reverse(path);
        return path;
    }
    public int getDistanceTo(int target) {
        this.graph.validateVertex(target);
        return this.distances[target];
    }
}
